package com.dq.offer;

/**
 * @Author: Dang Qi
 * @Date: 2021/3/15  22:47
 * @Description:
 */
public class NiXuDui {
    public static void main(String[] args) {
        int[] nums = {7,5,6,4};
        Solution solution = new NiXuDui().new Solution();
        System.out.println(solution.reversePairs(nums));
    }
    class Solution {
        public int reversePairs(int[] nums) {
            return mergeSort(nums, 0, nums.length - 1);
        }
        //[lo, hi]
        private int mergeSort(int[] nums, int lo, int hi){
            if(lo >= hi) return 0;
            int mid = (lo + hi) / 2;
            return mergeSort(nums, lo, mid) + mergeSort(nums, mid+1, hi) + merge(nums, lo, hi);
        }
        private int merge(int[] nums, int lo, int hi){
            int mid = (lo + hi) / 2;
            int r = 0;
            int[] helper = new int[hi-lo+1];
            for(int i = 0; i < hi - lo + 1; i++){
                helper[i] = nums[lo+i];
            }
            int i = lo - lo, j = mid + 1 - lo;
            int k = lo;
            while(i<=mid-lo && j<=hi-lo){
                if(helper[i] > helper[j]) {
                    r += hi-lo-j+1;
                    nums[k++] = helper[i++];
                }else{
                    nums[k++] = helper[j++];
                }
            }
            while(i<=mid-lo) nums[k++] = helper[i++];
            while(j<=hi-lo) nums[k++] = helper[j++];

            return r;
        }
    }
}
